#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int n;
int main()
{
	f[1] = 1;
	f[2] = 2;
	int idx = 0;
	bool f1 = 0;
	for (int i = 3; i <= N - 10; i++) {
		f[i] = f[i - 1] + f[i - 2];
		if (f[i] >= 1e5) {
			if (f1)f[i] %= 1000000;
			else {
				idx = i;
				f1 = 1;
			}
		}
	}
	//cout << "idx==" << idx << endl;
	while (cin >> n) {
		if (n < idx) printf("%d\n", f[n]);
		else printf("%06d\n", f[n]);
		
	}
	return 0;
}